package com.practice.zuocy.base.class07;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 实现二叉树的层序遍历：
 * （1）其实就是宽度优先遍历，用队列
 * （2）可以通过设置flag变量的方式，来发现某一层的结束
 */
public class Code03_LevelTraversalBT {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int v) {
			value = v;
		}
	}

	/**
	 * 用队列实现宽度优先遍历
	 *
	 * @param head 当前节点
	 */
	public static void level(Node head) {
		if (head == null) {
			return;
		}
		// 准备一个队列
		Queue<Node> queue = new LinkedList<>();
		// 当前节点进队列
		queue.add(head);
		// 队列不为空时：
		while (!queue.isEmpty()) {
			// 弹出一个节点并打印
			Node cur = queue.poll();
			System.out.println(cur.value);
			// 当前节点有左孩子，左孩子进队列
			if (cur.left != null) {
				queue.add(cur.left);
			}
			// 当前节点有右孩子，右孩子进队列
			if (cur.right != null) {
				queue.add(cur.right);
			}
		}
	}

	public static void main(String[] args) {
		Node head = new Node(1);
		head.left = new Node(2);
		head.right = new Node(3);
		head.left.left = new Node(4);
		head.left.right = new Node(5);
		head.right.left = new Node(6);
		head.right.right = new Node(7);

		level(head);
		System.out.println("========");
	}

}
